package mryao.tree;

import java.util.LinkedList;

public class binaryTree {


    protected treeNode<Integer> root;

    public binaryTree(){
        this.root = null;
    }

    public binaryTree(int value){
        this.root = new treeNode<Integer>(value);
    }

    public treeNode getRoot(){
        return root;
    }

    public void setRoot(treeNode<Integer> root) {
        this.root = root;
    }

    /**
     *          0
     *      1        2
     *    3  4      5
     */
    public void createTree(){
        treeNode bt1 = new treeNode(1);
        treeNode bt2 = new treeNode(2);
        treeNode bt3 = new treeNode(3);
        treeNode bt4 = new treeNode(4);
        treeNode bt5 = new treeNode(5);
        root.setLeft(bt1);
        root.setRight(bt2);
        root.getLeft().setLeft(bt3);
        root.getLeft().setRight(bt4);
        root.getRight().setLeft(bt5);
    }

    //逆90°树形打印
    public void treePrint(){
        System.out.println("\n逆90°树形打印:");
        treePrintHelper(-2,root);
    }

    private void treePrintHelper(int depth, treeNode currNode){
        if(currNode == null){
            return ;
        }
        treePrintHelper(++depth, currNode.getRight());
        for(int i=0; i<=depth; i++)
            System.out.print("       ");
        System.out.println(currNode);
        treePrintHelper(depth++, currNode.getLeft());
    }


    //先根 （根左右）
    public void preOrder(){
        System.out.println("\n先序递归打印:");
        preOrderHelper(root);
    }

    private void preOrderHelper(treeNode curNode){
        if(curNode != null) {
            System.out.print(curNode.getData() + " ");
            preOrderHelper(curNode.getLeft());
            preOrderHelper(curNode.getRight());
        }
    }

    public void nonPreOrder(){
        System.out.println("\n先序非递归打印:");
        //建立一个stack
        LinkedList<treeNode> stack = new LinkedList<treeNode>();
        treeNode currNode = root;
        //如过stack不为空  或者 当前node不为空
        while(currNode != null || !stack.isEmpty()){
            //如果当前node不为空
            if(currNode != null){
                //直接打印当前node （根）
                System.out.print(currNode + " ");
                //把打印过的node push到stack里面
                stack.addFirst(currNode);
                //然后打印根的left
                currNode = currNode.getLeft();
            }else {
                //如果 当前node 为空了 说明 node下面 没有东西了 需要把 node的上一级 拿出来
                currNode = stack.removeFirst();
                //把上一级的right给node 判断是否为空 为空 再向上找  不为空 则打印 以此循环
                currNode = currNode.getRight();
            }
        }
    }

    //中根 （左根右）
    public void inOrder(){
        System.out.println("\n中序递归打印:");
        inOrderHelper(this.root);
    }

    private void inOrderHelper(treeNode curNode){
        if(curNode != null){
            inOrderHelper(curNode.getLeft());
            System.out.print(curNode + " ");
            inOrderHelper(curNode.getRight());
        }
    }

    public void nonInOrder(){
        System.out.println("\n中序非递归打印:");
        treeNode currNode = root;
        LinkedList<treeNode> stack = new LinkedList<treeNode>();
        while(currNode != null || !stack.isEmpty()) {
            //如果当前结点不为空
            if(currNode != null){
                //push到stack里面
                stack.addFirst(currNode);
                //去找他的left node
                currNode = currNode.getLeft();
            }else{
                //如果node为空了 说明这是最左边的 打印它的上一级
                currNode = stack.removeFirst();
                System.out.print(currNode + " ");
                //再去找他的right的最左边的那一个
                currNode = currNode.getRight();
            }
        }
    }

    //后根 （左右根）
    public void postOrder(){
        System.out.println("\n后序递归打印:");
        postOrderHelper(root);
    }

    private void postOrderHelper(treeNode curNode) {
        if(curNode != null) {
            postOrderHelper(curNode.getLeft());
            postOrderHelper(curNode.getRight());
            System.out.print(curNode + " ");
        }
    }

    public void nonPostOrder(){
        System.out.println("\n后序非递归打印:");
        treeNode currNode = root;
        treeNode last = new treeNode();
        LinkedList<treeNode> stack = new LinkedList<treeNode>();
        while (currNode != null){
            while(currNode.getLeft() != null){
                //只要有左结点 直接下去
                stack.addFirst(currNode);
                currNode = currNode.getLeft();
            }
            while(currNode != null && (currNode.getRight() == null || currNode.getRight()== last)){
                //当前结点不为空 左边结点不可能为空 右边结点为空 或者等于上一个打印的结点
                System.out.print(currNode + " ");
                last = currNode;
                //返回上一级 如果有的话
                if(!stack.isEmpty()){
                    currNode = stack.removeFirst();
                }else{
                    return;
                }
            }
            //没有左结点了 就找右结点
            stack.addFirst(currNode);
            currNode = currNode.getRight();
        }
    }

    //广度优先 （层次） 父出子进
    public void breadthFirstTraverse(){
        System.out.println("\n层次打印");
        LinkedList<treeNode> queue = new LinkedList<treeNode>();
        treeNode<Integer> currNode = this.root;
        if(currNode != null) {
            queue.addLast(currNode);
            while (!queue.isEmpty()) {
                //父出
                currNode = queue.removeFirst();
                System.out.print(currNode + " ");
                //子进
                if(currNode.getLeft() != null)
                    queue.addLast(currNode.getLeft());
                if(currNode.getRight() != null)
                    queue.addLast(currNode.getRight());
            }
        }
    }
}
